//
//  BTree.hpp
//  DS_Demo
//
//  Created by apple on 2023/10/17.
//

#ifndef BTree_hpp
#define BTree_hpp

#include <stdio.h>
#include "DS_Define.h"


/*
 m阶B树的性质：
 1. B树的结点最多有 m 个 child，m-1 个key
 2. B树的根结点不是叶子结点，则至少有 2 个child
 3. B数除根节点以来的所有非叶子结点至少有 m/2向上取整 个 child，m/2向上取整-1 个 key
 4. 所有非叶子结点的结构: n|P0|K1|P1|K2|...|Kn|Pn|,
      1）其中n为当前结点的 key 的个数
      2）Ki(i=1,2,....n)为当前结点的 key，且K1<K2<K3<...<Kn
      3）Pi(i=0,1,2,...,n)为当前结点的 指向孩子结点的指针，
         且P(i-1)所指向孩子结点的所有所有关键字都小于Ki,
         Pi所指向孩子结点的所有关键字都大于Ki.
 5. 所有叶子结点都在同一层上
 
 已知B树为m阶，高为h，有n个结点，那么m、h和n之间关系为
        logm(n+1) <= h <= log[m/2]((n+1)/2) + 1, 其中[m/2]表示向上取整
 */
Status InitBTree(const BTree* bt, unsigned int dim);
Status DestroyBTree(const BTree* bt);
Status ClearBTree(const BTree* bt);
/*
 BTree的查找的实现步骤：
 
    1. 从根节点开始，逐一和根结点中的关键字进行比较。
    2. 如果能够找到，则查找成功，结束查找.
    3. 如果找不到，则如果待查找关键字key<K(min) || key>K(max) || K(i-1) < key < Ki,则进行如下步骤，
        3.1 如果 key<K(min)，则key与P(min-1)所指向的孩子结点中的关键字进行比较
        3.2 如果 key>K(max), 则key与P(max+1)所指向的孩子结点中的关键字进行比较
        3.3 如果 K(i-1)<key<Ki, 则key与Pi所指向的孩子结点中的关键字进行比较
    4. 重复3.1~3.3，如果匹配成功，则查找成功，结束查找；
       否则继续重复3.1～3.3直到到达叶子结点，此时表示查找失败。
 */
Status FindAntry(BTree bt, Antry elem);
/**
 BTree的删除操作实现步骤
    
 */
Status DeleteAntry(const BTree* bt, Antry elem);
/*
 BTree的插入操作实现步骤
 
1. 利用查找算法来，找出插入关键字的最底层的某个非叶子结点cur。（查找失败叶子结点的父结点即为我们需要的结点）
2. 将 key 按照某种算法插入到该非叶子结点cur当中，
    如果cur.n<=cur.min_dim-1, 则无须分裂，
    如果cur.n>cur.min_dim-1, 则溢出，需要进行分裂处理。分裂步骤如下：
        2.1 取cur关键字的中间位置[(1+n)/2]([]表示向上取整)，将其分成两个部分
        2.2 左边部分存放在原结点cur，右半部分放入新结点new，然后将中间位置的结点插入到parent。
        2.3 如果parent也产生溢出，则继续重复分裂操作，否则，插入完成，执行结束。
 */
Status InsertAntry(const BTree* bt, Antry elem);
void TraverseBTree(BTree bt);

#endif /* BTree_hpp */
